Search Results

Documents authored by Selivanov, Victor


Document
Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)

Authors: Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova

Published in: Dagstuhl Reports, Volume 11, Issue 10 (2022)


Abstract
Computability and continuity are closely linked - in fact, continuity can be seen as computability relative to an arbitrary oracle. As such, concepts from topology and descriptive set theory feature heavily in the foundations of computable analysis. Conversely, techniques developed in computability theory can be fruitfully employed in topology and descriptive set theory, even if the desired results mention no computability at all. In this Dagstuhl Seminar, we brought together researchers from computable analysis, from classical computability theory, from descriptive set theory, formal topology, and other relevant areas. Our goals were to identify key open questions related to this interplay, to exploit synergies between the areas and to intensify collaboration between the relevant communities.

Cite as

Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova. Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461). In Dagstuhl Reports, Volume 11, Issue 10, pp. 72-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Article{hoyrup_et_al:DagRep.11.10.72,
  author =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  title =	{{Descriptive Set Theory and Computable Topology (Dagstuhl Seminar 21461)}},
  pages =	{72--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{10},
  editor =	{Hoyrup, Mathieu and Pauly, Arno and Selivanov, Victor and Soskova, Mariya I.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.10.72},
  URN =		{urn:nbn:de:0030-drops-159293},
  doi =		{10.4230/DagRep.11.10.72},
  annote =	{Keywords: computable analysis, enumeration degrees, quasi-polish spaces, synthetic topology}
}
Document
Well Quasi-Orders in Computer Science (Dagstuhl Seminar 16031)

Authors: Jean Goubault-Larrecq, Monika Seisenberger, Victor Selivanov, and Andreas Weiermann

Published in: Dagstuhl Reports, Volume 6, Issue 1 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16031 "Well Quasi-Orders in Computer Science", the first seminar devoted to the multiple and deep interactions between the theory of Well quasi-orders (known as the Wqo-Theory) and several fields of Computer Science (Verification and Termination of Infinite-State Systems, Automata and Formal Languages, Term Rewriting and Proof Theory, topological complexity of computational problems on continuous functions). Wqo-Theory is a highly developed part of Combinatorics with ever-growing number of applications in Mathematics and Computer Science, and Well quasi-orders are going to become an important unifying concept of Theoretical Computer Science. In this seminar, we brought together several communities from Computer Science and Mathematics in order to facilitate the knowledge transfer between Mathematicians and Computer Scientists as well as between established and younger researchers and thus to push forward the interaction between Wqo-Theory and Computer Science.

Cite as

Jean Goubault-Larrecq, Monika Seisenberger, Victor Selivanov, and Andreas Weiermann. Well Quasi-Orders in Computer Science (Dagstuhl Seminar 16031). In Dagstuhl Reports, Volume 6, Issue 1, pp. 69-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{goubaultlarrecq_et_al:DagRep.6.1.69,
  author =	{Goubault-Larrecq, Jean and Seisenberger, Monika and Selivanov, Victor and Weiermann, Andreas},
  title =	{{Well Quasi-Orders in Computer Science (Dagstuhl Seminar 16031)}},
  pages =	{69--98},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{1},
  editor =	{Goubault-Larrecq, Jean and Seisenberger, Monika and Selivanov, Victor and Weiermann, Andreas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.1.69},
  URN =		{urn:nbn:de:0030-drops-58158},
  doi =		{10.4230/DagRep.6.1.69},
  annote =	{Keywords: Better quasi-order, Well quasi-order, Hierarchy, Infinite State Machines, Logic, Noetherian space, Reducibility, Termination, Topological Complexity,}
}
Document
Duality in Computer Science (Dagstuhl Seminar 15441)

Authors: Mai Gehrke, Achim Jung, Victor Selivanov, and Dieter Spreen

Published in: Dagstuhl Reports, Volume 5, Issue 10 (2016)


Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 15441 `Duality in Computer Science'. This seminar served as a follow-up seminar to the seminar `Duality in Computer Science' (Dagstuhl Seminar 13311). In this seminar, we focused on applications of duality to semantics for probability in computation, to algebra and coalgebra, and on applications in complexity theory. A key objective of this seminar was to bring together researchers from these communities within computer science as well as from mathematics with the goal of uncovering commonalities, forging new collaborations, and sharing tools and techniques between areas based on their common use of topological methods and duality.

Cite as

Mai Gehrke, Achim Jung, Victor Selivanov, and Dieter Spreen. Duality in Computer Science (Dagstuhl Seminar 15441). In Dagstuhl Reports, Volume 5, Issue 10, pp. 66-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{gehrke_et_al:DagRep.5.10.66,
  author =	{Gehrke, Mai and Jung, Achim and Selivanov, Victor and Spreen, Dieter},
  title =	{{Duality in Computer Science (Dagstuhl Seminar 15441)}},
  pages =	{66--88},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{10},
  editor =	{Gehrke, Mai and Jung, Achim and Selivanov, Victor and Spreen, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.10.66},
  URN =		{urn:nbn:de:0030-drops-56999},
  doi =		{10.4230/DagRep.5.10.66},
  annote =	{Keywords: coalgebra, domain theory, probabilistic systems, recognizability, semantics of non-classical logics, Stone duality}
}
Document
Duality in Computer Science (Dagstuhl Seminar 13311)

Authors: Mai Gehrke, Jean-Eric Pin, Victor Selivanov, and Dieter Spreen

Published in: Dagstuhl Reports, Volume 3, Issue 7 (2013)


Abstract
Duality allows one to move between the two worlds: the world of certain algebras of properties and a spacial world of individuals, thereby leading to a change of perspective that may, and often does, lead to new insights. Dualities have given rise to active research in a number of areas of theoretical computer science. Dagstuhl Seminar 13311 "Duality in Computer Science" was held to stimulate research in this area. This report collects the ideas that were presented and discussed during the course of the seminar.

Cite as

Mai Gehrke, Jean-Eric Pin, Victor Selivanov, and Dieter Spreen. Duality in Computer Science (Dagstuhl Seminar 13311). In Dagstuhl Reports, Volume 3, Issue 7, pp. 54-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{gehrke_et_al:DagRep.3.7.54,
  author =	{Gehrke, Mai and Pin, Jean-Eric and Selivanov, Victor and Spreen, Dieter},
  title =	{{Duality in Computer Science (Dagstuhl Seminar 13311)}},
  pages =	{54--73},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{7},
  editor =	{Gehrke, Mai and Pin, Jean-Eric and Selivanov, Victor and Spreen, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.7.54},
  URN =		{urn:nbn:de:0030-drops-43068},
  doi =		{10.4230/DagRep.3.7.54},
  annote =	{Keywords: Stone-Priestley duality, Point free topology, Infinite computations Exact real number computation, Computability in analysis, Hierarchies, Reducibilit Topological complexity, Domain theory, Semantics, Recognizability, Profinite topology}
}
Document
Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)

Authors: Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki

Published in: Dagstuhl Reports, Volume 1, Issue 10 (2012)


Abstract
There is a large gap between mathematical structures and the structures computer implementations are based on. To stimulate research to overcome this---especially for infinitary structures---highly non-trivial problem the Dagstuhl Seminar 11411 ``Computing with Infinite Data: Topological and Logical Foundations'' was held. This report collects the ideas that were presented and discussed during the course of the seminar.

Cite as

Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki. Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411). In Dagstuhl Reports, Volume 1, Issue 10, pp. 14-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Article{berger_et_al:DagRep.1.10.14,
  author =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  title =	{{Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)}},
  pages =	{14--36},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{10},
  editor =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.10.14},
  URN =		{urn:nbn:de:0030-drops-33721},
  doi =		{10.4230/DagRep.1.10.14},
  annote =	{Keywords: Exact real number computation, Stream computation, Infinite computations, Computability in analysis, Hierarchies, Reducibility, Topological complexity}
}
Document
10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees

Authors: Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas

Published in: Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)


Abstract
From 12.12.2010 to 17.12.2010, the Dagstuhl Seminar 10501 ``Advances and Applications of Automata on Words and Trees'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas. 10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{glasser_et_al:DagSemProc.10501.1,
  author =	{Glasser, Christian and Pin, Jean-Eric and Schweikardt, Nicole and Selivanov, Victor and Thomas, Wolfgang},
  title =	{{10501 Abstracts Collection – Advances and Applications of Automata on Words and Trees}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.1},
  URN =		{urn:nbn:de:0030-drops-31486},
  doi =		{10.4230/DagSemProc.10501.1},
  annote =	{Keywords: Automata theory, logic, verification, data structures, algorithms, complexity, games, infinite games with perfect information, reactive systems, specification and verification, combinatorics, hierarchies and reducibilities}
}
Document
10501 Executive Summary – Advances and Applications of Automata on Words and Trees

Authors: Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas

Published in: Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)


Abstract
The aim of the seminar was to discuss and systematize the recent fast progress in automata theory and to identify important directions for future research. For this, the seminar brought together more than 40 researchers from automata theory and related fields of applications. We had 19 talks of 30 minutes and 5 one-hour lectures leaving ample room for discussions. In the following we describe the topics in more detail.

Cite as

Christian Glasser, Jean-Eric Pin, Nicole Schweikardt, Victor Selivanov, and Wolfgang Thomas. 10501 Executive Summary – Advances and Applications of Automata on Words and Trees. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{glasser_et_al:DagSemProc.10501.2,
  author =	{Glasser, Christian and Pin, Jean-Eric and Schweikardt, Nicole and Selivanov, Victor and Thomas, Wolfgang},
  title =	{{10501 Executive Summary – Advances and Applications of Automata on Words and Trees}},
  booktitle =	{Advances and Applications of Automata on Words and Trees},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10501},
  editor =	{Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.2},
  URN =		{urn:nbn:de:0030-drops-31474},
  doi =		{10.4230/DagSemProc.10501.2},
  annote =	{Keywords: Infinite games with perfect information, reactive systems, specification and verification, combinatorics, hierarchies and reducibilities}
}
Document
08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
From June 29, 2008, to July 4, 2008, the Dagstuhl Seminar 08271 ``Topological and Game-Theoretic Aspects of Infinite Computations'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, many participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.1,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.1},
  URN =		{urn:nbn:de:0030-drops-16555},
  doi =		{10.4230/DagSemProc.08271.1},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification and verification, topological complexity, Wadge reducibility}
}
Document
08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
The theory of the infinite behaviour of continuously operating computing devices is of primary importance for several branches of theoretical and practical computer science. In particular, it is fundamental for the verification and synthesis of reactive systems like microprocessors or operating systems, for the understanding of dataflow computation, and for the development of adequate mathematical foundations for exact real computation. The seminar brought together researchers from many different disciplines who are working on theoretical or practical aspects of infinite computations. In this summary we describe the topics, the goals, and the contributions of the seminar.

Cite as

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.2,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.2},
  URN =		{urn:nbn:de:0030-drops-16499},
  doi =		{10.4230/DagSemProc.08271.2},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification}
}
Document
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

Authors: Christian Glasser, Heinz Schmitz, and Victor Selivanov

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: - The classes of the Boolean hierarchy over level $Sigma_1$ of the dot-depth hierarchy are decidable in $NL$ (previously only the decidability was known). The same remains true if predicates mod $d$ for fixed $d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then the classes of the Boolean hierarchy over level $Sigma_1$ are decidable. - For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level $Sigma_2$ of the Straubing-Th{'\e}rien hierarchy are decidable in $NL$. This is the first decidability result for this hierarchy. - The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for $NL$. - The membership problems for quasi-aperiodic languages and for $d$-quasi-aperiodic languages are logspace many-one complete for $PSPACE$.

Cite as

Christian Glasser, Heinz Schmitz, and Victor Selivanov. Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 337-348, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{glasser_et_al:LIPIcs.STACS.2008.1355,
  author =	{Glasser, Christian and Schmitz, Heinz and Selivanov, Victor},
  title =	{{Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{337--348},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1355},
  URN =		{urn:nbn:de:0030-drops-13554},
  doi =		{10.4230/LIPIcs.STACS.2008.1355},
  annote =	{Keywords: Automata and formal languages, computational complexity, dot-depth hierarchy, Boolean hierarchy, decidability, efficient algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail